In public key encryption that is presently widely used for safely transmitting information via public communication lines, safety is secured by a computation amount of classic computers. Furthermore, in quantum encryption (quantum key allocation) that has heretofore been suggested, such as BB84, unconditional safety is secured, provided that authentication is correctly performed. However, with the above-described methods, safety is not secured in a case where a quantum computer is used. A research such as described in Non-patent Document 1 below relates to a public key protocol that uses a quantum system. Non-patent Document 1: A. Kawachi et al, Proc. EUROCRYPT 2005, LNCS 3494, 268, 2005.